package year2023.dp;

public class Code06_ConvertToLetterString {

    //规定1和A对应， 2和B对应， 3和C对应....26和Z对应
    //那么一个数字字符串比如“111”就可以转化为
    //“AAA” , “KA” 和 “AK”
    //给定一个只有数字字符组成的字符串str,返回有多少种转化结果
    public static int number(String str){
        if (str == null || str.length() == 0){
            return 0;
        }
        return process(str.toCharArray(),0);
    }

    public static int process(char[] str, int i) {
        if (i == str.length){
            return 1;
        }
        // i 没到最后，说明有字符
        if (str[i] == '0'){//之前的决定有问题，返回0种方法。
            return 0;
        }
        // str[i] != ’0‘
        //可能性1 让i单独转换
        int ways = process(str, i + 1);
        //可能性2 让i和i+1共同转换(不一定都有)
        if (i+1 < str.length && (str[i] - '0') * 10 + (str[i+1] - '0') < 27){
            ways += process(str, i + 2);
        }
        return ways;

    }

    public static int dp(String s){
        if (s == null || s.length() == 0){
            return 0;
        }
        char[] str = s.toCharArray();
        int N = str.length;

        int[] dp = new int[N + 1];
        dp[N] = 1;
        for (int i = N - 1; i >= 0 ; i--) {

            if (str[i] != '0'){
                int ways = dp[i + 1];
                //可能性2 让i和i+1共同转换(不一定都有)
                if (i+1 < str.length && (str[i] - '0') * 10 + (str[i+1] - '0') < 27){
                    ways += dp[i + 2];
                }
                dp[i] = ways;
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        System.out.println(number("111"));
        System.out.println(dp("111"));
    }


}
